package j2024.j202411;

import java.util.Random;

public class j1130 {
    /**
     * 215. 数组中的第K个最大元素
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     *
     * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     *
     * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
     * @param nums
     * @param l
     * @param r
     */
    public void swap(int[] nums,int l,int r){
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;
    }
    public int findKthLargest(int[] nums, int k) {
        return qqsort(nums, 0, nums.length - 1, k);
    }

    public int qqsort(int[] nums,int l,int r,int k){
        if(l==r){
            return nums[l];
        }
        int key = nums[new Random().nextInt(r-l+1)+l];
        int left = l-1,right = r+1,i = l;
        while(i<right){
            if(nums[i]<key){
                swap(nums,++left,i++);
            }else if(nums[i]==key){
                i++;
            }else {
                swap(nums,--right,i);
            }
        }
        //分类讨论[l,left][left+1,right-1][right,r]
        int b = right-1-left-1+1;
        int c = r-right+1;
        //判断k在哪个区间
        if(c>=k){
            return qqsort(nums,right,r,k);
        } else if (c+b>=k) {
            return key;
        }else {
            return qqsort(nums,l,left,k-b-c);
        }
    }
}
